Bỉ có trận đấu chính thức đầu tiên vào ngày 1 tháng 5 năm 1904 là trận hoà 3-3 trước đội tuyển Pháp. Trước trận đấu này, đội tuyển chọn lọc của Bỉ có thi đấu vài trận, nhưng trong đội hình có một số cầu thủ Anh, do đó không được tính là trận đấu chính thức. Ví dụ Bỉ thắng Hà Lan 8-0 ngày 28 tháng 4 năm 1901 với sự có mặt của vài cầu thủ Anh. Sau trận đấu này, hai nước láng giềng Bỉ và Hà Lan có truyền thống một năm đấu 2 trận bắt đầu từ năm 1905, thường được tổ chức ở Antwerp và Rotterdam (sau chuyển sang Amsterdam). Vào thời điểm đó, đội tuyển Bỉ thường do 1 ban tuyển lựa quyết định gồm đại diện của 6 hoặc 7 câu lạc bộ lớn.

Biệt danh Những con quỷ đỏ của đội tuyển Bỉ do phóng viên Pierre Walckiers đặt cho sau trận thắng 3-2 trước Hà Lan (Rotterdam, 1906).

Hơn sáu thập kỉ sau, Bỉ trở thành một trong những đội bóng mạnh, tuy không vô địch các giải đấu lớn nhưng đối thủ không dễ vượt qua họ, kể cả ở sân nhà hay sân khách. Chìa khoá thành công của đội tuyển là việc sử dụng bẫy việt vị, một chiến thuật phòng ngự được phát triển trong thập niên 1960, ban đầu tại câu lạc bộ Anderlecht của huấn luyện viên người Pháp Pierre Sinibaldi.

Thế hệ vàng (1980-2002)

Giai đoạn thập niên 1980 và đầu thập niên 1990 là thời gian mạnh nhất trong lịch sử của Bỉ. Thành tích cao nhất của họ trong giai đoạn này là á quân Euro 1980. Dưới sự chỉ đạo của huấn luyện viên dày dạn kinh nghiệm Guy Thys, người từng chỉ đạo hơn 100 trận đấu chính thức, Bỉ nổi tiếng là 1 đội tuyển tổ chức tốt, thể lực sung mãn, 1 đối thủ khó vượt qua.

Đội tuyển có những cầu thủ trình độ cao như thủ môn Jean-Marie Pfaff, hậu vệ phải Eric Gerets, tiền vệ Jan Ceulemans, và tiền vệ kiến thiết Enzo Scifo. Tuy có một vài trận đấu không tốt với các đối thủ yếu hơn, nhưng họ thường đấu hay khi gặp các đối thủ mạnh. Cho đến tận gần đây, năm 2002, các đội bóng hàng đầu thế giới cũng ngại chạm trán với Những con quỷ đỏ, thậm chí cả nhà vô địch World Cup 2002, đội tuyển Brasil cũng phải chật vật mới thắng Bỉ 2-0 ở trận đấu loại trực tiếp trong giải này. Tuy nhiên kể từ đó, đội tuyển Bỉ dần xuống phong độ, chưa tìm lại được danh tiếng thuở trước.

Thoái trào và hi vọng mới (2003-2011)

Sau khi thất bại tại vòng loại World Cup 2006 (lần đầu tiên sau 24 năm), huấn luyện viên Aimé Anthuenis không được gia hạn hợp đồng, và René Vandereycken thay thế Anthuenis từ 1 tháng 1 năm 2006. Tuy vậy ông cũng không đưa được đội tuyển Bỉ vượt qua vòng loại Euro 2008, chỉ xếp thứ 5 ở bảng đấu loại.

Thế hệ vàng mới (2012-nay)

Bỉ hiện tại có hàng loạt cầu thủ chuyên môn tốt như các tiền đạo Mirallas, Benteke, Lukaku, Batshuayi, các tiền vệ Fellaini, Witsel, Carrasco, Dembele, De Bruyne, Nainggolan, Mertens và Hazard. Hàng thủ cũng rất mạnh với các cầu thủ nổi danh Kompany, Vermaelen, Alderweireld, Vertonghen cùng các thủ môn Courtois và Mignolet.